#include<bits/stdc++.h>	
using namespace std;
//* Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};
// Function to create a linked list from an array  
ListNode* createLinkedList(const vector<int>& nums) {
	if (nums.empty()) return nullptr;
	ListNode* head = new ListNode(nums[0]);
	ListNode* tail = head;
	for (size_t i = 1; i < nums.size(); ++i) {
		tail->next = new ListNode(nums[i]);
		tail = tail->next;
	}
	return head;
}

// Function to print the linked list  
void printLinkedList(ListNode* head) {
	while (head != nullptr) {
		cout << head->val << " ";
		head = head->next;
	}
	cout << endl;
}
class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		stack<ListNode*> nodes;
		ListNode* t = head;
		if (!head || head->next == nullptr) return head;
		while (t) {
			nodes.push(t);
			t = t->next;
		}
		head = nodes.top();
		while (!nodes.empty()) {
			t = nodes.top();
			nodes.pop();
			if (nodes.empty())
				t->next = nullptr;
			else
				t->next = nodes.top();
		}
		return head;
	}
};
int main206() {
	// Test the reverseList function  
	vector<int> nums = { 1, 2, 3, 4, 5 };
	ListNode* head = createLinkedList(nums);
	cout << "Original linked list: ";
	printLinkedList(head);

	Solution solution;
	ListNode* reversedHead = solution.reverseList(head);
	cout << "Reversed linked list: ";
	printLinkedList(reversedHead);

	// Clean up memory (optional, depending on your environment)  
	// Note: This is a simplified cleanup and assumes no cycles in the list  
	ListNode* current = reversedHead;
	while (current != nullptr) {
		ListNode* temp = current;
		current = current->next;
		delete temp;
	}

	return 0;
}